package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         378,
		Discription: "有序矩阵中的第k小元素",
		Level:       2,
		Labels: map[string]int{
			"二分查找": 1,
			"分界查找": 1,
		},
	})
}

/*
为什么最后的left一定在矩阵中：
假设left不在矩阵中，那么矩阵中有k-1各元素小于left，left为第k小
那么left前面必有一个x，使得矩阵中<=x的元素有k个，x自己为第k小
所以，在二分时，如果有<=x的值刚好为k个，最终的答案一定<=x，所以right=mid
*/
func KthSmallest(matrix [][]int, k int) int {
	m := len(matrix)
	n := len(matrix[0])
	//统计矩阵中<=val的值的个数
	notBiggerCount := func(val int) int {
		i := m - 1
		j := 0
		count := 0
		for i >= 0 && j <= n-1 {
			if matrix[i][j] <= val {
				count += i + 1
				j++
			} else {
				i--
			}
		}

		return count
	}

	left := matrix[0][0]
	right := matrix[m-1][n-1]
	for left < right {
		//一定得这么写，要不然容易循环
		mid := left + (right-left)/2
		if notBiggerCount(mid) < k {
			left = mid + 1
		} else {
			//易错
			right = mid
		}
	}

	return left
}
